UVa/11338 - Minefield/11338.3.cpp

   1 #include <iostream>
   2 #include <vector>
   3 #include <queue>
   4 #include <map>
   5 #include <cmath>
   6 #include <sstream>
   7 #include <functional>
   8
   9 using namespace std;
  10
  11 const double infinity = 1E20;
  12
  13 struct point{
  14   double x, y;
  15   point(double X, double Y){ x = X; y = Y;}
  16 };
  17
  18 map< point, double > dist;
  19
  20 bool operator ==(const point &a, const point &b){ return (a.x == b.x && a.y == b.y);}
  21 bool operator !=(const point &a, const point &b){ return !(a == b);}
  22 bool operator <(const point &a, const point &b){ return (a.x < b.x || (a.x == b.x && a.y < b.y));}
  23 //bool operator <(point a, point b){ return (a.dist > b.dist);}
  24 double distancia(point a, point b){return hypot(a.y-b.y, a.x-b.x);}
  25
  26
  27
  28 bool heapCmp(const point &a,const point &b){
  29   return (dist[a] > dist[b]);
  30 }
  31
  32
  33 struct heapCompare : public binary_function<point, point, bool>
  34 {
  35   bool operator()(const point &x, const point &y) const
  36   { return dist[x] > dist[y]; }
  37 };
  38
  39
  40 struct grafo{
  41   //contiene todos los nodos sueltos
  42   vector<point> nodos;
  43   //contiene un vector con todos los vecinos para el punto point
  44   map< point, vector<point> > vecinos;
  45
  46   void insert(point a){
  47     if (vecinos.count(a) == 1) return; //Ya insertamos este nodo
  48     nodos.push_back(a);
  49     vector<point> v;
  50     vecinos.insert(make_pair(a, v));
  51     //printf("Insertando (%f,%f).\n", a.x, a.y);
  52   }
  53
  54   void make_vecinos(double maxPath){
  55     for (map< point, vector<point> >::iterator it=vecinos.begin(); it!=vecinos.end(); ++it){
  56       if (distancia((*it).first, point(0.00, 0.00)) > maxPath){
  57         //printf("El punto (%f,%f) es un desastre.\n", (*it).first.x, (*it).first.y);
  58         continue;
  59       }
  60       for (map< point, vector<point> >::iterator jt = it; jt!=vecinos.end(); ++jt){
  61         //Insertarlo como vecino en los nodos diferentes a el mismo
  62         //printf("  Ensayando (*it).first = (%f,%f)\n", (*it).first.x, (*it).first.y);
  63         if ((*it).first != (*jt).first){
  64           if ((*jt).first.x - (*it).first.x > 1.5){
  65             //printf("Rompiendo con a = (%f,%f) y nodos[i] = (%f,%f)\n", a.x, a.y, (*it).first.x, (*it).first.y);
  66             break;
  67           }
  68           vector<point> adj = vecinos[(*it).first];
  69           //Asegurarse de no insertar un vecino repetido
  70           //    if (find(adj.begin(), adj.end(), a) == adj.end()){
  71           if (distancia((*jt).first, (*it).first) <= 1.5){
  72             //printf("Insertando (%f,%f) como vecino de (%f,%f).\n", a.x, a.y, (*it).first.x, (*it).first.y);
  73             vecinos[(*it).first].push_back((*jt).first);
  74             vecinos[(*jt).first].push_back((*it).first);
  75           }
  76           //    }
  77         }
  78       }
  79     }
  80   }
  81
  82   void initialize(){
  83     dist.clear();
  84     for (int i=0; i<nodos.size(); ++i){
  85       dist[nodos[i]] = infinity;
  86       if (nodos[i].x == 0.00 && nodos[i].y == 0.00){
  87         dist[nodos[i]] = 0.00;
  88       }
  89     }
  90   }
  91
  92   /*void relax(point u, point v){
  93     if (dist[v] > dist[u] + distancia(u, v)){
  94       dist[v] = dist[u] + distancia(u, v);
  95     }
  96     }*/
  97
  98   void dijkstra(const double &maxPath, const point &finalPoint){
  99     initialize();
 100
 101     //priority_queue<point, vector<point>, heapCompare > q(nodos.begin(), nodos.end());
 102     priority_queue<point, vector<point>, heapCompare > q;
 103     q.push(point(0.0, 0.0));
 104     //vector<point> q(nodos.begin(), nodos.end());
 105     //make_heap(q.begin(), q.end(), heapCmp);
 106     while (!q.empty()){
 107       //point u = q.front();
 108       //pop_heap(q.begin(), q.end(), heapCmp); q.pop_back();
 109       point u = q.top();
 110       q.pop();
 111       //printf("Saque (%f,%f) cuya distancia es %f\n", u.x, u.y, dist[u]);
 112       if (distancia(point(0.00, 0.00), u) + distancia(u, finalPoint) <= maxPath){
 113         for (int i=0; i<vecinos[u].size(); ++i){
 114           point v = vecinos[u][i];
 115           //printf("  Comparando (%f,%f) con (%f,%f) que estan a %f\n", u.x, u.y, v.x, v.y, distancia(u,v));
 116           //printf(" dist[u] es %f, dist[v] es %f\n", dist[u], dist[v]);
 117           if (dist[vecinos[u][i]] > (dist[u] + distancia(u,v))){
 118             //printf("  Actualizando la distancia de v = (%f,%f)\n", v.x, v.y);
 119             dist[vecinos[u][i]] = dist[u] + distancia(u, v);
 120             //printf("  Nueva distancia de v: %f\n", dist[v]);
 121             q.push(v);
 122           }
 123         }
 124       }
 125       //make_heap(q.begin(), q.end(), heapCmp);
 126     }
 127   }
 128
 129 };
 130
 131
 132
 133 int main(){
 134   while (true){
 135
 136     string s;
 137     for (s = ""; s == ""; getline(cin, s));
 138     if (s == "*") break;
 139
 140
 141     grafo g;
 142
 143     stringstream line;
 144     line << s;
 145
 146     int w,h;
 147     line >> w >> h;
 148     g.insert(point((double)w, (double)h));
 149     g.insert(point(0.00, 0.00));
 150     int noPuntos;
 151     cin >> noPuntos;
 152     for (int i=0; i<noPuntos; ++i){
 153       double x,y;
 154       cin >> x >> y;
 155       g.insert(point(x,y));
 156     }
 157
 158
 159     double maximoCamino;
 160     cin >> maximoCamino;
 161
 162     g.make_vecinos(maximoCamino);
 163     //cout << "Termine de insertar todos los nodos.\n";
 164
 165     /*printf("Voy a imprimir el grafo de %d nodos:\n", g.nodos.size());
 166     for (int i=0; i<g.nodos.size(); ++i){
 167       printf("Estos son los vecinos de (%f,%f):\n", g.nodos[i].x, g.nodos[i].y);
 168       for (int j=0; j<g.vecinos[g.nodos[i]].size(); ++j){
 169         printf("  (%f,%f)\n", g.vecinos[g.nodos[i]][j].x, g.vecinos[g.nodos[i]][j].y);
 170       }
 171       }*/
 172
 173     g.dijkstra(maximoCamino, point((double)w, (double)h));
 174     //printf("La distancia minima hasta (%d,%d) es %f.\n", w,h,dist[point((double)w, (double)h)]);
 175     if (dist[point((double)w, (double)h)] <= maximoCamino){
 176       printf("I am lucky!\n");
 177     }else{
 178       printf("Boom!\n");
 179     }
 180
 181   }
 182   return 0;
 183 }